7503. Олимпиада

На олимпиаду по информатике прибыли n команд по a_i (1 ≤ i ≤ n) участников в каждой. Для проведения соревнований приготовили классы с одинаковым количеством m компьютеров в каждом. Какое минимальное количество классов необходимо задействовать при условии, что в каждом классе будут представители только разных команд. То есть ни в каком классе не должно находится более одного участника из одной команды.

Вход. В первой строке заданы числа n и m. Во второй строке находятся n чисел a_i (1 ≤ i ≤ n). Числовые значения целые, неотрицательные и не превышают 100.

Выход. Выведите одно число – необходимое количество классов.

Пример входа	Пример выхода
5 3 2 3 4 1 2	4

РЕШЕНИЕ

циклы

Анализ алгоритма

Всего на соревнование прибыло s = участников. Поскольку каждая комната содержит m компьютеров, то потребуется как минимум комнат. Пусть p – наибольшее количество участников от одной команды (максимальное значение среди всех A_i). Если p > , то нам потребуется как минимум p комнат. Конструктивно можно показать, что max(, p) классов всегда будет достаточно для проведения олимпиады.

Пример

На олимпиаду прибыло 2 + 3 + 4 + 1 + 2 = 12 школьников. В каждом классе находится m = 3 компьютера, поэтому для олимпиады необходимо задействовать как минимум 12 / 3 = 4 класса.

Максимальное количество участников имеется от третьей команды, оно равно 4, которых по одному можно рассадить в 4 класса.

Например, следующая рассадка участников является одной из допустимых.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d",&n,&m);

Вычисляем общее число участников s, а также размер p наибольшей команды.

p = 0;

for (i = 0; i < n; i++)

{

scanf("%d",&x);

s += x;

if (x > p) p = x;

}

Значение res = вычисляем как (s + m – 1) / m.

res = (s + m - 1) / m;

Если p > , то ответом будет значение p.

if (res < p) res = p;

Выводим ответ.

printf("%d\n",res);